class ACNode{
    children = new Array(26)
    fail = null
    exist = []
    val = ''
    constructor(val){
        this.val = val
    }
}

const root = new ACNode('root')

// 构建 trie 树
function insert(str){
    let node = root
    let newNode = null
    for (let i = 0; i < str.length; i++) {
        const index = str.codePointAt(i) - 'a'.codePointAt()
        if(!node.children[index]){
            newNode = new ACNode(str[i])
            node.children[index] = newNode
        }
        node = node.children[index]
    }
    newNode.exist = [str.length]
}
// bsf 初始化 fail
function buildFailPointer(root){
    const queue = [root]
    while(queue.length > 0){
        const current = queue.shift()
        current.children.forEach(child=>{
            if(current.fail){
                const index = child.val.codePointAt() - 'a'.codePointAt()
                const fail = current.fail.children[index]
                child.fail = fail ? fail : root
            }else{
                child.fail = root
            }
            if(child.exist.length > 0 && child.fail.exist > 0){child.exist.push(...child.fail.exist)}
            queue.push(child)
        })
    }
}

function query(str){
    const res = []
    let start = root
    for (let i = 0; i < str.length; i++) {
        const charIndex = str.codePointAt(i) - 'a'.codePointAt()
        const node = start.children[charIndex]
        if(node){
            if(node.exist.length > 0){
                node.exist.forEach(index => {
                    res.push(str.substr(i - index + 1 ,index))
                })
            }
            start = node.children.some(item => item !== null)? node : node.fail
        }else{
            start = root
        }
    }
    return res
}

const arr = ['he','she','hers','his']
for (let i = 0; i < arr.length; i++) {
    insert(arr[i])
}
buildFailPointer(root)
console.log(query('ahishexrhisehe'))
